Tuple spaces provide a unique form of flexibility in the sharing of information and the coordination of applications. As described in greater detail below, tuples are collections of key-value pairs stored in a tuple space that can be queried based on the matching of anti-tuples by tuples. The original Linda model by David Gelernter (N. Carriero and D. Gelernter, “Linda in context”, Communications of the ACM 32(4):444-458, Apr. 1989) has found widespread use in collaborative systems. However, tuple spaces have typically been implemented in software, which is inadequate for the scalability and responsiveness of fine-grained and large-scale systems.
The use of custom designed hardware to implement models of fine-grained and large-scaled systems also suffers from a number of disadvantages. Firstly, memory management problems arise since tuples may be of any length and may be inserted and deleted freely in the tuple space, with the result that a fragmented memory structure is created having variable length gaps left where tuples have been removed. This, in turn, creates difficulty in determining where to put new tuples or anti-tuples in the memory.
Secondly, it is difficult to accommodate parallel searching while maintaining reasonable hardware complexity. Also, it is difficult to design specific hardware for the hardware tuple space system so as to scale to very large memory sizes without incurring significant increases in complexity and cost.
The need for hardware assistance to enable improved scalability and responsiveness for a tuple space has been recognized in the World Wide Web Consortium and is reported in the paper Tuplets: Words for a Tuple Space Machine by Duncan Campbell. This is a technical report for the Computer Science Department at York and has been designated YCS-97.
Campbell describes the use of a content-addressable memory (CAM) for the implementation of a tuple space. CAMs are accessed by the content of their memory rather than by direct addressing which is advantageous in the case of a tuple search since the memory will return the record associated with the content presented to it which is a natural solution for matching. However, as discussed above, Campbell identifies a major problem that arises in memory management in the case of variable length fields in tuples spaces.
As Campbell correctly points out, since tuples are collections of key-value pairs the number of keys can be restricted so that hashing can be used to produce constant length representations of the keys for the memory. However, in practical applications the values cannot be so restricted. Campbell devises a scheme that he refers to as Tuplets wherein fields (containing both keys and values) can be broken up into fixed length groupings for storage in the memory. This is analogous to the ATM method of segmenting longer length packets into fixed length cells for switching, based on the premise that such segmenting produces more regular and implementable hardware solutions. Tuplets (as with ATM cells) can be reassembled into tuples (packets) when needed.
One difficulty with the Tuplet/Cam solution provided by Campbell is that content searching is complex and requires a very large amount of silicon hardware and real estate to implement. This problem is particularly important in systems that are used for fine-grained control of system operation. Conventional tuple spaces are implemented in software and used for coarse-grained coordination of applications. In such systems, relatively few tuples are used and coordination is relatively infrequent. Such systems are used to communicate between applications (e.g. start one application when another finishes, etc.) However, opportunities now exist for tuple spaces to coordinate the fine-grained behavior of systems wherein applications modify their actions based on current user and network context, the operations of other applications, etc. Such fine-grained behavior control may be applied to systems such as telephone networks, networks of PDAs, etc. A relatively much larger number of tuples are used in such systems and at relatively much faster rates. Hardware solutions are attractive in such applications due to their speed. Although Campbell's tuplet solution meets the speed criteria, it suffers from major deficiencies in terms of cost and in scaling to the relatively larger sizes required by fine-grained applications. Solutions to these problems must scale well with the number of users and be of low cost.